// ============================================================================
//
// LCP-net framework by Pierre CHATEL chatelp@gmail.com
// Distributed under GPLv3
// Copyright (C) THALES Land & Joint Systems, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.preferenceFramework.algorithms;

import java.util.Iterator;

import com.thalesgroup.graphFramework.core.Edge;
import com.thalesgroup.graphFramework.core.Graph;
import com.thalesgroup.graphFramework.core.Vertex;


public class DepthBasedWeights {

	public static final String depthKey	 = "com.thalesgroup.preferenceFramework.algorithms.DepthBasedWeights.depth";
	public static final String weightKey = "com.thalesgroup.preferenceFramework.algorithms.DepthBasedWeights.weight";
	
	/**
	 * Run the depth-based weights computation algorithm on the specified graph.
	 * @param graph the graph to process.
	 */
	public static <V, E> void run(Graph<V, E> graph) {
		computeDepths(graph);
		computeWeights(graph, DefaultDistribution.INSTANCE);
		normalizeWeights(graph);
	}
	
	/**
	 * Compute each of the graph's nodes depth.
	 * @param graph the graph to process.
	 */
	private static <V, E> void computeDepths(Graph<V, E> graph) {

		//a - Fix all initial depths to 1.0
		for (Iterator<Vertex<V, E>> i = graph.getVertices(); i.hasNext();) {
			Vertex<V, E> v = i.next();

			v.setUserFeature(depthKey, 1.);
		}

		//b - Run iteration edges x vertices times
		for (int k = 0; k < graph.getEdgesSize(); k++) {
			for (Iterator<Vertex<V, E>> i = graph.getVertices(); i.hasNext();) {
				Vertex<V, E> tgt = i.next();

				Double max = 0.;
				for (Iterator<Edge<V, E>> j = tgt.getIns(); j.hasNext();) {
					Vertex<V, E> src = j.next().getIn();
					Double local = (Double) src.getUserFeature(depthKey);
						if (local > max)
							max = local;
				}
				//set new target node's depth
				tgt.setUserFeature(depthKey, max + 1);
			}
		}
	}
	
	/**
	 * Compute each of the graph's nodes weight according to its depth and a distribution.
	 * @param graph the graph to process.
	 * @param distrib a depth->weight distribution. 
	 */
	private static <V,E> void computeWeights(Graph<V,E> graph, Distribution distrib) {
		double maxDepth =0;

		for (Iterator<Vertex<V, E>> i = graph.getVertices(); i.hasNext();) {
			Vertex<V, E> tgt = i.next();
			double depth=(Double) tgt.getUserFeature(depthKey);
			if(depth>maxDepth) maxDepth=depth;
		}

		double[] dom=distrib.getInputDomain();
		
		double a= (dom[1]-dom[0])/(maxDepth-1);
		double b= dom[0]+(dom[0]-dom[1])/(maxDepth-1);
	
		for (Iterator<Vertex<V, E>> i = graph.getVertices(); i.hasNext();) {
			Vertex<V, E> tgt = i.next();
			double depth=(Double) tgt.getUserFeature(depthKey);
			//handle special case where max depth == 1 (err: division by 0)
			if(maxDepth == 1) {
				//we (arbitrarily) choose the lower limit of the distribution when depth == 1
				tgt.setUserFeature(weightKey, distrib.f(dom[0]));
			} else {
				tgt.setUserFeature(weightKey, distrib.f(a*depth+b));
			}
		}
	}
	
	/**
	 * Normalize weights so that their sum = 1.
	 * @param graph graph to normalize.
	 */
	private static <V, E> void normalizeWeights(Graph<V, E> graph) {
		double sum=0;
		
		for (Iterator<Vertex<V, E>> i = graph.getVertices(); i.hasNext();) {
			Vertex<V, E> tgt = i.next();
			sum+=(Double) tgt.getUserFeature(weightKey);
		}
		
		for (Iterator<Vertex<V, E>> i = graph.getVertices(); i.hasNext();) {
			Vertex<V, E> tgt = i.next();
			tgt.setUserFeature(weightKey, ((Double) tgt.getUserFeature(weightKey))/sum);
		}	
	}
}
